package class_2;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Coding_quickSort2 {
	public static void quickSort(int[] arr) {
		if(arr==null || arr.length<2) {
			return ;
		}
		quick(arr,0, arr.length-1);
	}
	static class Tuple{
		int first;
		int last;
		public Tuple(int first,int last) {
			this.first = first;
			this.last = last;
		}
		public Tuple() {
			
		}
	}
	public static Tuple tuple = new Tuple();//辅助partition。
	public static void quick(int[] arr, int l,int r) {
		//l==r, l>r直接返回， 不用处理。
		if(l>=r) {
			return ;
		}
		//随机取[l,r]的一个数 nums[?]
		int x = arr[l+(int)(Math.random()*(r-l+1))];
		
		partition(arr,l,r,x);
		quick(arr,l,tuple.first-1);
		quick(arr,tuple.last,r);
	}
	/**
	 * partition 方法的目的是根据给定的基准（pivot）将数组分成两部分：
	 * 一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
	 * 该方法的返回结果是新的分区边界，以便在快速排序中递归调用。
	 * @param arr 数组
	 * @param l 左端点
	 * @param r 右端点
	 * @param x 随机选取的枢轴
	 */
	public static void partition(int[] arr, int l, int r, int x) {
	    tuple.first = l; // 小于区域的右边界
	    tuple.last = r;  // 大于区域的左边界
	    int i = l;       // 当前元素指针

	    while (i <= tuple.last) {
	        if (arr[i] == x) {
	            // 当前元素等于主元，移动指针
	            i++;
	        } else if (arr[i] < x) {
	            // 当前元素小于主元，交换到小于区域
	            swap(arr, tuple.first++, i++);
	        } else {
	            // 当前元素大于主元，交换到大于区域
	        	// 注意这里i不变。
	            swap(arr, tuple.last--, i);
	        }
	    }
	}

	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static int MAX = 3000;
	public static void main(String[] args) {
		  	Random random = new Random(100);
	        int[] arr = new int[MAX];
	        System.out.printf("输入规模:%d\n",MAX);
	        // 测试重复数字的情况
	        for (int i = 0; i < MAX; i++) {
	            arr[i] = random.nextInt(10000);
	        }
	        System.out.println("排序前:" + Arrays.toString(arr));
	        long startTime = System.nanoTime();
	        quickSort(arr);
	        long endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试无重复数字的情况
	        random.setSeed(0);
	        Set<Integer> set = new HashSet<>();
	        while (set.size() < MAX) {
	            set.add(random.nextInt(10000));
	        }
	        int i = 0;
	        for (int x : set) {
	            arr[i++] = x;
	        }
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("不出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试完全相同的情况
	        Arrays.fill(arr, 5);
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现完全相同的重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");
	        System.out.println("--------------------------------");
	}
}
